package com.cqs.leetcode.string;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * lixw
 * 2021/11/21
 **/
public class LongestWordDictionary720 {
    public String longestWord(String[] words) {
        Arrays.sort(words, (o1, o2) -> {
            if (o1.length() != o2.length()) return o1.length()-o2.length();
            return o1.compareTo(o2);
        });
        Set<String> prefix = new HashSet<>();
        prefix.add("");
        String result = "";
        for(String word:words) {
            String s = word.substring(0,word.length()-1);
            if (prefix.contains(s)) {
                if (result.length() < word.length()) {
                    result = word;
                }else if (result.length() == word.length() && word.compareTo(result) < 0) {
                    result = word;
                }
                prefix.add(result);
            }
        }
        return result;
    }
}
